C语言迪杰斯特拉算法的实现

2024-07-17 03:58| 来源: 网络整理| 查看: 265

迪杰斯特拉算法用于求图的最短路径。下面是实现代码：

首先，预定义和类型定义：

#define OK 1 #define ERROR 0 #define MVNum 100 #define Max_Int 32726 typedef int Status; typedef int ArcType; typedef char VerTexType; typedef struct{ VerTexType vex[MVNum]; ArcType arc[MVNum][MVNum]; int vexnum, arcnum; }AMGraph;

并声明两个全局变量：

int Path[MVNum]; ArcType D[MVNum];

Path[]用于记录上一步节点，D[]用于记录最短路径的权值。

创建有向图：

int LocateVex(AMGraph *G, VerTexType v) { int i; for (i = 0; i < G->vexnum; i++) { if (G->vex[i] == v) return i; } return -1; } Status CreateUDN(AMGraph *G) { VerTexType v1, v2; ArcType w; int i, j, k; printf("输入总节点数、总边数："); scanf("%d %d", &G->vexnum, &G->arcnum); printf("输入节点的值："); fflush(stdin); for (i = 0; i < G->vexnum; i++) { scanf("%c", &G->vex[i]); } for (i = 0; i < G->vexnum; i++) for (j = 0; j < G->vexnum; j++) { G->arc[i][j] = Max_Int; } for (k = 0; k < G->arcnum; k++) { fflush(stdin); printf("依次输入边的两个顶点以及边的权值："); scanf("%c %c %d", &v1, &v2, &w); i = LocateVex(G, v1); j = LocateVex(G, v2); G->arc[i][j] = w; } return OK; }

迪杰斯特拉算法：

void ShortestPath_DIJ(AMGraph G, int v0) { int min, i, w, v; bool S[MVNum]; for (v = 0; v < G.vexnum; v++) { S[v] = false; D[v] = G.arc[v0][v]; if (D[v] < Max_Int) Path[v] = 0; else Path[v] = -1; } S[v0] = true; D[v0] = 0; for (i = 1; i < G.vexnum; i++) { min = Max_Int; for (w = 0; w < G.vexnum; w++) { if (!S[w] && min>D[w]) { v = w; min = D[w]; } } S[v] = true; for (w = 0; w < G.vexnum; w++) { if (!S[w] && D[w]>D[v] + G.arc[v][w]) { D[w] = D[v] + G.arc[v][w]; Path[w] = v; } } } }

声明一个bool类型数组S[]记录该节点是否已经处于最短路径。用for()循环将S[]初始化为false，表明并未求出最短路径，D[]初始化为各个节点到初始节点v0的边的权值，如果权值小于最大值（Max_Int）则说明两个节点之间有边，Path[]为0，否则没有路径，Path[]为-1。让v0下标的S[]为true，表示当前已经是最短路径，并将其最短路径D[]赋值为0。

让最小权值min为Max_Int，利用for()循环筛选出权值最短并且另一个节点尚未遍历的边，下标记录为v。筛选出来后让下标为v的S[]为true，表明已经是最短路径。然后用for()循环检查最短路径：如果下标为w的节点尚未求出最短路径并且D[]中记录w的权值大于D[v]加上v和w边权值之和，则让D[w]的值为D[v]加v和w边权值之和，并将v记录在Path[w]中。

重复上一段操作。

加入main()：

int main(void) { int i, j; AMGraph G; CreateUDN(&G); ShortestPath_DIJ(G, 0); for (i = 1; i < G.vexnum; i++) { if (D[i] == Max_Int) printf("0无法到达%c\n", G.vex[i]); else printf("0到%c的权值为：%d\n", G.vex[i], D[i]); } return 0; }

【本文地址】

公司简介

联系我们